package problem164_Maximum_Gap;

import java.util.Arrays;

/**
 *  如果是平均分布，则桶的数目和元素的数目相同时，其排序的时间复杂度是0(n)
 *  假设桶的个数和元素的数目相同，若是平均分布，则每个桶里有一个数，而若某个桶里有两个以上的数时（n个数字，至少n个桶），
 *  这时必有至少一个是空桶，那么最大间隔可能就落在空桶的相邻两个桶存储的数之间，最大间隔不会落在同一个桶的数里，
 *  因此我们不需要对每个桶再排一次序，只需要记录同一个桶的最大值和最小值，算出前一个有最大值的桶和后一个有最小值的桶之差，
 *  则可能是最大间隔
 *
 */
public class Solution {
	 public int maximumGap(int[] nums) {
		 if(nums.length<2)
			 return 0;
		 int max=nums[0],min=nums[0];
		 for(int i=1;i<nums.length;i++){
			 max=Math.max(max, nums[i]);
			 min=Math.min(min, nums[i]);
		 }
		 int gap=(max-min)/(nums.length-1);
		 if(gap==0)gap++;
		 int[] minBukets=new int[(max-min)/gap+1];
		 int[] maxBukets=new int[(max-min)/gap+1];
		 Arrays.fill(minBukets, Integer.MAX_VALUE);
		 Arrays.fill(maxBukets, Integer.MIN_VALUE);
		 for(int n:nums){
			 int index=(n-min)/gap;
			 minBukets[index]=Math.min(n, minBukets[index]);
			 maxBukets[index]=Math.max(n, maxBukets[index]);
		 }
		 int previous=min;int result=0;
		 for(int i=0;i<minBukets.length;i++){
			 if(minBukets[i]==Integer.MAX_VALUE||maxBukets[i]==Integer.MIN_VALUE)
				 continue;
			 result=Math.max(result, minBukets[i]-previous);
			 previous=maxBukets[i];
		 }
		 return result;
	 }
	 
	 public static void main(String[] args){
		 System.out.println(new Solution().maximumGap(new int[]{1,1,1,100}));
	 }
}
